-- 多个坐标的中心点计算和分组
local CoordinateGrouping = {}

-- 计算两点之间的距离
function CoordinateGrouping.getDistance(x1, y1, x2, y2)
    local dx = x2 - x1
    local dy = y2 - y1
    return math.sqrt(dx * dx + dy * dy)
end

-- 计算一组坐标的中心点
function CoordinateGrouping.getCenterPoint(coordinates)
    if not coordinates or #coordinates == 0 then
        return nil, nil
    end

    local sumX, sumY = 0, 0
    for _, coord in ipairs(coordinates) do
        sumX = sumX + coord.x
        sumY = sumY + coord.y
    end

    local centerX = sumX / #coordinates
    local centerY = sumY / #coordinates

    return centerX, centerY
end


-- 将距离相近的坐标分组
-- coordinates: 坐标数组，每个元素包含 {x = x值, y = y值}
-- threshold: 距离阈值，小于此距离的坐标会被分为一组
function CoordinateGrouping.groupByDistance(coordinates, threshold)
    if not coordinates or #coordinates == 0 then
        return {}
    end

    threshold = threshold or 200 -- 默认阈值200
    local groups = {}
    local used = {}              -- 标记已被分组的坐标

    for i = 1, #coordinates do
        if not used[i] then
            local group = { coordinates[i] }
            used[i] = true

            -- 查找与当前坐标距离小于阈值的其他坐标
            for j = i + 1, #coordinates do
                if not used[j] then
                    local distance = CoordinateGrouping.getDistance(
                        coordinates[i].x, coordinates[i].y,
                        coordinates[j].x, coordinates[j].y
                    )

                    if distance <= threshold then
                        table.insert(group, coordinates[j])
                        used[j] = true
                    end
                end
            end

            table.insert(groups, group)
        end
    end

    return groups
end

-- 使用层次聚类算法进行分组（更精确的分组方法）
function CoordinateGrouping.groupByHierarchical(coordinates, threshold)
    if not coordinates or #coordinates == 0 then
        return {}
    end

    threshold = threshold or 200
    local groups = {}

    -- 初始化，每个坐标为一个独立的组
    for _, coord in ipairs(coordinates) do
        table.insert(groups, { coord })
    end

    local changed = true
    while changed and #groups > 1 do
        changed = false
        local minDistance = math.huge
        local mergeI, mergeJ = -1, -1

        -- 找到距离最近的两个组
        for i = 1, #groups do
            for j = i + 1, #groups do
                local distance = CoordinateGrouping.getGroupDistance(groups[i], groups[j])
                if distance < minDistance then
                    minDistance = distance
                    mergeI, mergeJ = i, j
                end
            end
        end

        -- 如果最小距离小于阈值，则合并两个组
        if minDistance <= threshold and mergeI ~= -1 and mergeJ ~= -1 then
            -- 合并组
            for _, coord in ipairs(groups[mergeJ]) do
                table.insert(groups[mergeI], coord)
            end
            table.remove(groups, mergeJ)
            changed = true
        end
    end

    return groups
end

-- 计算两个组之间的最小距离
function CoordinateGrouping.getGroupDistance(group1, group2)
    local minDistance = math.huge

    for _, coord1 in ipairs(group1) do
        for _, coord2 in ipairs(group2) do
            local distance = CoordinateGrouping.getDistance(
                coord1.x, coord1.y, coord2.x, coord2.y
            )
            if distance < minDistance then
                minDistance = distance
            end
        end
    end

    return minDistance
end

-- 获取所有组的中心点
function CoordinateGrouping.getGroupsCenterPoints(groups)
    local centerPoints = {}

    for i, group in ipairs(groups) do
        local centerX, centerY = CoordinateGrouping.getCenterPoint(group)
        if centerX and centerY then
            table.insert(centerPoints, {
                x = centerX,
                y = centerY,
                groupIndex = i,
                groupSize = #group
            })
        end
    end

    return centerPoints
end

-- 示例使用函数
function CoordinateGrouping.example()
    -- 示例坐标数据
    local coordinates = {
        { x = 100,  y = 100 },
        { x = 100,  y = 200 },
        { x = 100,  y = 300 },
        { x = 100,  y = 400 },
        { x = 100,  y = 500 },
        { x = 1000, y = 600 },
        { x = 100,  y = 700 },
        { x = 100,  y = 800 }
    }

    print("原始坐标数量:", #coordinates)

    -- 使用距离分组
    local groups = CoordinateGrouping.groupByHierarchical(coordinates, 400)
    print("分组数量:", #groups)

    -- 获取每组的中心点
    local centerPoints = CoordinateGrouping.getGroupsCenterPoints(groups)

    for i, centerPoint in ipairs(centerPoints) do
        print(string.format("第%d组: 中心点(%.2f, %.2f), 包含%d个坐标",
            i, centerPoint.x, centerPoint.y, centerPoint.groupSize))
    end

    return groups, centerPoints
end

--CoordinateGrouping.example()

return CoordinateGrouping
